import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

/**
 * 56. 合并区间
 *
 * 给出一个区间的集合，请合并所有重叠的区间。
 *
 *
 *
 * 示例 1:
 *
 * 输入: intervals = [[1,3],[2,6],[8,10],[15,18]]
 * 输出: [[1,6],[8,10],[15,18]]
 * 解释: 区间 [1,3] 和 [2,6] 重叠, 将它们合并为 [1,6].
 *
 * 示例 2:
 *
 * 输入: intervals = [[1,4],[4,5]]
 * 输出: [[1,5]]
 * 解释: 区间 [1,4] 和 [4,5] 可被视为重叠区间。
 *
 * 注意：输入类型已于2019年4月15日更改。 请重置默认代码定义以获取新方法签名。
 *
 *
 *
 * 提示：
 *
 *     intervals[i][0] <= intervals[i][1]
 *
 *
 *  贪心算法：
 *
 *  首先按照区间的起始大小对所有区间进行排序,，这样后面比较的时候就不需要去比较起始位置了
 *
 *  previous current两个指针:
 *
 *  可能出现的情况：
 *      ① 可以合并：
 *          更新previous区间的结尾部分，另其等于current区间的结尾
 *          current指向下一个区间
 *      ② 不可以合并(current[0] > previous[1])：
 *          把previous指向的区间加入结果当中，并让其指向current所指向的区间
 *
 */
public class Solution_056 {
    public int[][] merge(int[][] intervals) {
        //先按区间起始位置进行排序
        Arrays.sort(intervals,(i1, i2)->{
            return Integer.compare(i1[0],i2[0]);
        });

        //最开始为null
        int [] previous = null;
        List<int[]> result = new ArrayList<>();

        for (int[] current:intervals){
            //如果是第一个节点或者不可以合并，则加入到结果中区
            if (previous == null || current[0] > previous[1]){
                result.add(previous = current);
            }else {
                //可以合并，更新previous的范围
                previous[1] = Math.max(current[1],previous[1]);
            }
        }
        return result.toArray(new int[result.size()][]);
    }
}
